package com.duing.greedy;

public class CanJump {

    public static void main(String[] args) {
        //int[] nums = {2, 3, 1, 1, 4};
        int[] nums = {3, 2, 1, 0, 4};
        System.out.println(canJump(nums));
    }

    // [2,3,1,1,4]
    //  遍历过程  更新最远可以到达的索引位置
    // index  nums[index]     cur    result
    //  0         2            2       2
    //  1         3            4       4
    //  2         1            3       4
    //  3         1            4       4

    // [3,2,1,0,4]
    //  遍历过程  更新最远可以到达的索引位置
    // index  nums[index]     cur    result
    //  0         3            3        3
    //  1         2            3        3
    //  2         1            3        3
    //  3         0            3        3
    //  4

    // 时间复杂度  O(n)
    // 空间复杂度  O(1)
    public static boolean canJump(int[] nums) {
        // 最远可达的索引位置
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            // 遍历到了不可达的位置
            if (i > result) break;
            // 当前节点可达的最远位置
            int cur = i + nums[i];
            // 如果cur更大 赋值给result 否则不变
            result = Math.max(cur, result);

            System.out.printf("i = %d , cur = %d , result = %d", i, cur, result);
            System.out.println();
            if (result >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}
